package com.bjpowernode.java;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wuyuecai
 * @create 2021-05-29 19:20
 */
public class Solution {
        /*
        给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 
        的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，
        数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
        示例 1：
        输入：nums = [2,7,11,15], target = 9
        输出：[0,1]
        解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

         */
        //第一种方法 时间复杂度O(N^2),空间复杂度O(1)
        public int[] twoSum1(int[] nums, int target) {
            for(int i = 0;i < nums.length-1;i++){
                for (int j = i+1; j < nums.length; j++) {
                    if(target == (nums[i]+nums[j])){
                        //返回i和j的数组首地址
                        return new int[]{i,j};
                    }
                }
            }
            //返回一个空的数组首地址
            return new int[0];
        }
        //第二种方法 时间复杂度O(n),空间复杂度O(n)
        public int[] twoSum2(int[] nums, int target) {
            //使用多次的值用变量表示
            int len = nums.length;
            //这里HashMap的初始化容量为len-1的原因是：哈希表中最多存len-1个数据，最坏的情况是最后一个找到target-x的值，这时就不用存到哈希表中了
            Map<Integer,Integer> hashMap = new HashMap<>(len-1);
            for (int i = 0; i < len; i++) {
                int another = target-nums[i];
                if(hashMap.containsKey(another)){
                    return new int[]{hashMap.get(another),i};
                }
                //如果another的值不在哈希表中那么就把这个数据添加到哈希表中
                hashMap.put(nums[i],i);
            }
            return new int[0];
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            int[] nums = {6,1,8,2,3};
            int[] a = solution.twoSum2(nums,8);
            for (int i = 0; i < a.length; i++) {
                System.out.println(a[i]);
            }
        }
}
